This invention relates to a constraint application processor, of the kind employed to apply linear constraints to signals obtained in parallel from multiple sources such as arrays of radar antennas or sonar transducers.
Constraint application processing is known, as set out for example by Applebaum (Reference A.sub.1) at page 136 of "Array Processing Applications to Radar", edited by Simon Haykin, published by Hughes, Dowden Hutchinson and Ross Inc. 1980. Reference A.sub.1 describes the case of adaptive sidelobe cancellation in radar, in which the constraint is that one (main) antenna has a fixed gain, and the other (subsidiary) antennas are unconstrained. This simple constraint has the form W.sup.T C=.mu., where the transpose of C is C.sup.T, the row vector [0, 0, . . . 1], W.sup.T is the transpose of a weight vector W and .mu. is a constant. For many purposes, this simple constraint is inadequate, it being advantageous to apply a constraint over all antenna signals from an array.
A number of schemes have been proposed to extend constraint application to include a more general constraint vector C not restricted to only one non-zero element.
In Reference A.sub.1, Applebaum also describes a method for applying a general constraint vector for adaptive beamforming in radar. Beam-forming is carried out using an analog cancellation loop in each signal channel. The k.sup.th element C.sub.k of the constraint vector C is simply added to the output of the k.sup.th correlator, which, in effect defines the k.sup.th weighting coefficient W.sub.k for the k.sup.th signal channel. However, the technique is only approximate, and can lead to problems of loop instability and system control difficulties.
In Widrow et al (Reference A.sub.2), at page 175 of "Array Processing Applications to Radar" (cited earlier), the approach is to construct an explicit weight vector incorporating the constraint to be applied to array signals. The Widrow LMS (least mean square) algorithm is employed to determine the weight vector, and a so-called pilot signal is used to incorporate the constraint. The pilot signal is generated separately. It is equal to the signal generated by the array in the absence of noise and in response to a signal of the required spectral characteristics received by the array from the appropriate constraint direction. The pilot signal is then treated as that received from a main fixed gain antenna in a simple sidelobe cancellation configuration. However, generation of a suitable pilot signal is very inconvenient to implement. Moreover, the approach is only approximate; convergence corresponds to a limit never achieved in practice. Accordingly, the constraint is never satisfied exactly.
Use of a properly constrained LMS algorithm has also been proposed by Frost (Reference A.sub.3), at page 238 of "Array Processing Applications to Radar" (cited earlier). This imposes the required linear constraint exactly, but signal processing is a very complex procedure. Not only must the weight vector be updated according to the basic LMS algorithm every sample time, but it must also be multiplied by the matrix P=I-C(C.sup.T C).sup.-1 C.sup.T, and added to the vector F=.mu.C(C.sup.T C). Here I is the unit diagonal matrix, C the constraint vector and T the conventional symbol indicating vector transposition.
A further discussion on the application of constraints in adaptive antenna arrays is given by Applebaum and Chapman (Reference A.sub.4), at page 262 of "Array Processing Applications to Radar" (cited earlier).
It has been proposed to apply beam constraints in conjunction with direct solution algorithms, as opposed to gradient or feedback algorithms. This is set out in Reed et al (Reference A.sub.5), at page 322 of "Array Processing Applications to Radar" (cited earlier), and makes use of the expression: EQU MW=C*, where C* is the complex conjugate of C. (1)
Equation (1) relates the optimum weight vector W to the constraint vector C and the covariance matrix M of the received data. M is given by: EQU M=X.sup.T X (2)
where X is the matrix of received data or complex signal values, and X.sup.T is its transpose. Each instantaneous set of signals from an array of antennas or the like is treated as a vector, and successive sets of these signals or vectors form the matrix X. The covariance matrix M expresses the degree of correlation between, for example, signals from different antennas in an array. Equation (2) is derived analytically by the method of Langrangian undetermined multipliers. The direct application of equation (1) involves forming the covariance matrix M from the received data matrix X, and, since the constraint vector C is a known precondition, solving for the weight vector W. This approach is numerically ill-conditioned, ie division by small and therefore inaccurate quantities may be involved, and a complicated electronic processor is required. For example, solving for the weight vector involves storing each element of the covariance matrix M, and retrieving it from or returning it to the appropriate storage location at the correct time. This is necessary in order to carry out the fixed sequence of arithmetic operations required for a given solution algorithm. This involves the provision of complicated circuitry to generate the correct sequence of instructions and addresses. It is also necessary to store the matrix of data X while the weight vector is being computed, and subsequently to apply the weight vector to each row of the data matrix in turn inorder to produce the required array residual.
Other direct methods of applying linear constraints, do not form the covariance matrix M, but operate directly on the data matrix X. In particular, the known modified Gram-Schmidt algorithm reduces X to a triangular matrix, thereby producing the inverse Cholesky square root factor G of the covariance matrix. The required linear constraint is then applied by invoking equation (2) appropriately. However, this leads to a cumbersome solution of the form W=G(S*G).sup.T, which involves computation of two successive matrix/vector products.
In "Matrix Triangularisation by Systolic Arrays", Proc. SPIE., Vol 28, Real-Time Signal Processing IV (1981) (Reference B), Kung and Gentleman employed systolic arrays to solve least squares problems, of the kind arising in adaptive beamforming. A QR decomposition of the data matrix is produced such that: EQU QX=[R/O] (3)
where R is an upper triangular matrix. The decomposition is performed by a triangular systolic array of processing cells. When all data elements of X have passed through the array, parameters computed by and stored in the processing cells are routed to a linear systolic array. The linear array performs a back-substitution procedure to extract the required weight vector W corresponding to a simple constraint vector [0, 0, 0 . . . 1] as previously mentioned. However, the solution can be extended to include a general constraint vector C. The triangular matrix R corresponds to the Cholesky square root factor of Reference B and so the optimum weight vector for a general constraint takes the form RW=Z, where R.sup.T Z=C*. These can be solved by means of two successive triangular back-substitution operations using the linear systolic array referred to above. However the back-substitution process can be numerically ill-conditioned, and the need to use an additional linear systolic array is cumbersome. Furthermore, back-substitution produces a single weight vector W for a given data matrix X. It is not recursive as required in many signal processing applications, ie there is no means for updating W to reflect data added to X.